This invention relates to the field of computer memory management, and in particular to the problem of efficiently performing computer garbage collection in real-time.
Computer programs typically make use of variables or similar labels to reference data xe2x80x9cobjects.xe2x80x9d A portion of computer memory must be allocated during execution to each such object. Over time, as many such objects are created and used, the available, xe2x80x9cfreexe2x80x9d memory that remains to be allocated in a particular system may begin to run short. As is well known in the art, a variety of methods and techniques have been proposed and implemented to reclaim as xe2x80x9cfreexe2x80x9d and available those portions of computer memory that were originally allocated to program objects that are no longer in use by any running program. This task is generally known in the art as xe2x80x9cgarbage collection.xe2x80x9d A great variety of different garbage collection techniques have been developed and used; for example, the reference paper Uniprocessor Garbage Collection Techniques by Paul R. Wilson (available through Internet via anonymous FTP from cs.utexas.edu as pub/garbage/bigsurv.ps) provides a broad survey of existing techniques, and explains commonly used terminology. That paper is incorporated herein in its entirety by this reference.
Prior art garbage collection systems have generally suffered to various degrees from the problem of excessive pause times. This problem arises when garbage collection is performed in real-time, i.e., concurrently with the execution of other live programs running on one or more processors. (In the field of garbage collection, the other live programs are typically referred to as xe2x80x9cmutators,xe2x80x9d because such programs potentially xe2x80x9cmutatexe2x80x9d or change the state of memory, from the point of view of the garbage collector or xe2x80x9cGC.xe2x80x9d)
For example, suppose that a system contains multiple mutator threads and a single GC thread. (A xe2x80x9cthreadxe2x80x9d is an execution context within a shared address space, as discussed further below.) If the mutators are, for example, trying to present a movie at 30 frames per second, and they require a combined time of 23 ms to generate each frame, then problems will arise if the GC thread is run for more than 10 ms during any particular 33 ms interval. It would therefore be desirable in this scenario to guarantee that the garbage collector will run no more than 30 times per second (i.e., its frequency will be no greater than 30; equivalently, its period will be greater than or equal to 33 ms), and also that each time the garbage collector is run it will execute for a maximum duration of no more than 10 ms.
GC frequency and duration can of course be kept xe2x80x9climitedxe2x80x9d through brute force, in the sense that the execution time allotted to the GC program may be explicitly rationed under control of the operating system or some other scheduling manager. This does not solve the problem at hand, however, because garbage collectors generally perform certain non-deferable, atomic work that must not be interrupted by mutators, at the risk of causing potential memory corruption. For example, a well-known family of GC schemes known as xe2x80x9ccopyingxe2x80x9d collectors (described in the Wilson survey paper, for example) actually copy, to a new location in memory, each data object that is determined not to be garbage (i.e., the object may still be in use by a live program). Since each such data object can potentially be arbitrarily large, and because the copying operation is necessarily atomic, a copying garbage collector may enter a phase where it cannot be interrupted by any mutator for an arbitrarily long period of time. Such GC schemes are generally not satisfactory for real-time systems where a maximum GC duration is required.
While non-copying garbage collectors also exist in the prior art (e.g., Henry G. Baker Jr., The Treadmill: Real-Time Garbage Collection Without Motion Sickness, SIGPLAN Notices Vol. 27 No. 3 at pp. 66-70, March 1992, incorporated herein in its entirety by this reference), many current applications of interestxe2x80x94notably, in the realm of multimediaxe2x80x94require limits on the maximum frequency and duration of garbage collection that the prior art has so far failed to dependably satisfy, at least on general-purpose stock hardware. As a result, systems running multimedia applications and the like have so far been unable to use garbage collection, and have instead been forced to rely on inconvenient, manual storage management techniques.
The present invention disclosed herein provides a novel method and apparatus for real-time garbage collection that offers unprecedented low bounds on the worst-case for GC frequency and duration.
Briefly, the present invention is used with a plurality of objects and with one or more mutators. The mutators, and the garbage collector itself, run on one or more computer processors, as scheduled by a scheduler. Stock hardware may be used; i.e., special purpose hardware is not necessary. The mutators each have a corresponding thread with a corresponding thread state. In the present invention, execution of all mutators is temporarily restricted at the start of each new garbage collection cycle. However, unrestricted and concurrent execution of each mutator is resumed, as soon as that mutator""s thread state is processed by the garbage collector.
In another feature of the present invention, the mutators are executed subject to a protective write barrier. However, the write barrier does not have to be applied to the modification of any mutator thread states, yielding valuable performance benefits.